/*
 * =====================================================================================
 *
 *       Filename:  CStack.h
 *
 *    Description:  CStack.h
 *
 *         Author:  Younghyun Jo
 *   Organization:  Master Student
 *                  Computer Systems and Platforms Laboratory
 *                  Department of Computer Science and Engineering
 *                  Seoul National University
 *
 * =====================================================================================
 */

#include <tmc/spin.h>
#include <tmc/sync.h>
#include <arch/atomic.h>
#include <arch/inline.h>
#include <sys/time.h>

#define item_t uint64_t

class Node {
  public:
    Node();
    Node(const item_t value);
    ~Node(void);

    const item_t _value;
    Node* _next;
    Node* _prev;
};

class CStack {
  public:
    CStack();
    virtual ~CStack(void);

    virtual bool Push(int value, int thread_id);
    virtual item_t Pop(void);
    virtual Node* Peek(void);
    virtual void Display(void);

  protected:
    //int _size; // the number of entries in the stack
                 // we don't use this value to remove the
                 // synchronization overheads to increment this value
    Node* _head; // point to start of the stack
    Node* _top; // point to top of the stack
    int _size; // the number of participants
};


//--------------------------------------------------------------------------------------
// CCoarseGrainedLockStack, CLockFreeStack
//

#define lock_init(lock) tmc_spin_mutex_init(lock)
#define lock_destruct(lock) {;} // nothing
#define lock_acquire tmc_spin_mutex_lock
#define lock_release tmc_spin_mutex_unlock
#define lock_t tmc_spin_mutex_t

class CCoarseGrainedLockStack : public CStack {
  public:
    CCoarseGrainedLockStack();
    virtual ~CCoarseGrainedLockStack(void);

    virtual bool Push(int value, int thread_id);
    virtual item_t Pop(void);

  protected:
    lock_t _lock; // the coarse grained lock
                  // on Tilera, it is actually tmc_spin_mutex_t
                  // tmc_spin_mutex_t is a basic spin lock built-in
};

class CLockFreeStack : public CStack {
  public:
    CLockFreeStack();
    virtual ~CLockFreeStack(void);

    virtual bool Push(int value, int thread_id);
    virtual item_t Pop(void);

  protected:
};

//--------------------------------------------------------------------------------------
// CEliminationBackoffStack
//

#define EMPTY 0
#define WAITING 1
#define BUSY 2
#define NOITEM 0

// it just send TimeoutException signal
class TimeoutException {
  public:
    TimeoutException() {}
    ~TimeoutException() {}
};

class CTimeUnit {
  public:
    long long GetTimeStamp(void); // return the system time
};

class CRandom {
  public:
    CRandom() { srand((unsigned)NULL); }
    
    int nextInt(int range) {
      return rand()%range;
    }
};

class CRangePolicy {
  public:
    CRangePolicy(int range);
    ~CRangePolicy();

    int GetRange();
    void RecordEliminationSuccess();
    void RecordEliminationTimeout();

  private:
    int _range; // the number of range size for elimination array
    unsigned long _success; // the number of elimination backoff successes
    unsigned long _timeout; // the number of elimination backoff timeouts
};

// it mimics the AtomicStampedReference functionality in JAVA
class CAtomicStampedReference {
  public:
    CAtomicStampedReference();
    ~CAtomicStampedReference();

    bool CompareAndSet(item_t yrItem, item_t myItem, int beforeState, int nextState);
    item_t Get(int* stampHolder);
    void Set(item_t item, int newStamp);

  private:
    item_t _item;
    //int _state; // state = { EMPTY, WAITING, BUSY }
                  // state is actually 3 bits, and it is located in
                  // [63:62] bits in _item's Virtual Address
};

class CLockFreeExchanger {
  public:
    CLockFreeExchanger();
    ~CLockFreeExchanger();

    item_t Exchange(item_t myItem, long long timeout, CTimeUnit* unit);

  private:
    CAtomicStampedReference* _slot;
};

class CEliminationArray {
  public:
    CEliminationArray(int capacity, long long timeout);
    ~CEliminationArray();

    CLockFreeExchanger** exchanger;
    item_t visit(item_t node, int range);

  private:
    CRandom* _random;
    CTimeUnit* _timeUnit;
    long long _duration;
    int _capacity;
};

class CEliminationBackoffStack : public CStack {
  public:
    CEliminationBackoffStack();
    CEliminationBackoffStack(int capacity, long long timeout); // explicit capacity
    virtual ~CEliminationBackoffStack(void);

    virtual bool Push(int value, int thread_id);
    virtual item_t Pop(void);

  protected:

  private:
    CEliminationArray* _eliminationArray;
    CRangePolicy* _rangePolicy; // range policy
    int _capacity; // capacity for the elimination array
    long long _timeout; // timeout value for the elimination array
};

//--------------------------------------------------------------------------------------
// CCombTreeStack
//

#define spin_lock_init(lock) tmc_spin_mutex_init(lock)
#define spin_lock_destruct(lock) {;} // nothing
#define spin_lock_acquire tmc_spin_mutex_lock
#define spin_lock_release tmc_spin_mutex_unlock
#define spin_lock_t tmc_spin_mutex_t

#define cond_lock_init(lock) tmc_spin_cond_init(lock)
#define cond_lock_destruct(lock) {;} // nothing
#define cond_lock_wait tmc_spin_cond_wait_spin
#define cond_lock_timeWait  tmc_spin_cond_timedwait_spin
#define cond_lock_signal tmc_spin_cond_signal
#define cond_lock_signalAll tmc_spin_cond_broadcast
#define cond_lock_t tmc_spin_cond_t

class TreeInput {
  public:
    enum TreeInputType { PUSH, POP };

    TreeInput(Node* node);
    ~TreeInput();

    bool IsPush() { return _oper == PUSH; }
    bool IsPop() { return _oper == POP; }

    Node* _node; // push operation contains it, pop takes the node from push operation
    enum TreeInputType _oper; // whether it is push or pop

    TreeInput* _prev;
    TreeInput* _next;
};

class CTreeInputList {
  public:
    CTreeInputList();
    CTreeInputList(TreeInput* input);
    virtual ~CTreeInputList();

    TreeInput* _headPush; // point to start of the push operations
    TreeInput* _topPush; // point to top of the pop operations
    TreeInput* _headPop; // point to start of the push operations
    TreeInput* _topPop; // point to top of the pop operations
};

class ScopeLock {
  public:
    explicit ScopeLock(spin_lock_t* lock) : _lock(lock) { spin_lock_acquire(_lock); }
    ~ScopeLock() { spin_lock_release(_lock); } 
  private:
    spin_lock_t* _lock;
    ScopeLock(ScopeLock&);
    ScopeLock& operator=(ScopeLock&);
};

class TreeNode {
  friend class CCombTreeStack;
  public:
    enum Cstatus { IDLE, FIRST, SECOND, RESULT, ROOT };

    TreeNode();
    ~TreeNode();
    TreeNode(TreeNode* myParent);
    TreeNode* GetParent();

  private:
    bool _locked; // locked status on this nodes
    spin_lock_t _nodeLock; // for synchronization method
    cond_lock_t _cond; // for pthread_cond_t

    enum Cstatus _cStatus; // combining status

    CTreeInputList* _firstValue; // this stack contains head and top pointers
    CTreeInputList* _secondValue;
    CTreeInputList* _result;

    TreeNode* _parent;

    bool PreCombine();
    CTreeInputList* Combine(CTreeInputList* combined);
    CTreeInputList* Op(CTreeInputList* combined);
    void Distribute(CTreeInputList* prior);

    CTreeInputList* Merge(CTreeInputList* first, CTreeInputList* second);
};

class CCombTreeStack {
  public:
    CCombTreeStack(int size); // size: the number of threads
    ~CCombTreeStack();

    virtual bool Push(int value, int thread_id);
    virtual item_t Pop(int thread_id);

    CTreeInputList* VisitTree(int thread_id, CTreeInputList* list);
    int GetResult();

  private:
    int _treeSize;

    TreeNode** _leaf; // point to the leaf nodes
    TreeNode** _nodes; // point to the root nodes
};

